package br.ufpe.abaco.ParserGen.parser;

/**
 *  Esta classe calcula quais simbolos nao-terminais derivam a string vazia
 *  (epsilon).
 *
 *@author     Monique Monteiro e Pablo Sampaio
 *@created    30 de Outubro de 2002
 */
class Nullables  implements java.io.Serializable {
    private BNFGrammar gramatica;
    private boolean[] isNull;

    private boolean[] calculados;
    private int[] prodEmCalculo;


    //producoes em calculo associadas a cada um dos nao-terminais

    /**
     *  Constructor for the Nullables object
     *
     *@param  grammar  Description of the Parameter
     */
    public Nullables(BNFGrammar grammar) {
        int numNonTerm = grammar.getNumNonTerminals();

        this.gramatica = grammar;
        this.isNull = new boolean[numNonTerm];
        this.calculados = new boolean[numNonTerm];
        this.prodEmCalculo = new int[numNonTerm];

        for (int i = 0; i < numNonTerm; i++) {
            this.calculados[i] = true;
        }

        this.calculateNullables();

        this.calculados = null;
        this.prodEmCalculo = null;
    }


    /**
     *  Description of the Method
     */
    public void calculateNullables() {
        Production[] productions = this.gramatica.getAllProductions();
        NonTerminalSymbol left;
        GrammarSymbol[] right;
        int i;
        int j;
        int tamanho;
        int next = 0;

        forExterno :
        for (i = 0; i < productions.length; i++) {
            left = productions[i].getLeftSide();
            right = productions[i].getRightSide();

            //se o lado direito da producao eh null,
            //entao o nao-terminal do lado esquerdo deriva null (obvio)
            if (right.length == 0) {
                this.isNull[left.index] = true;
                //a producao atual eh removida do array (nao verdade, ela nao eh reinserida)

            } else {

                for (j = 0; j < right.length; j++) {
                    //se no lado direito da producao aparecer algum terminal ou
                    //se aparecer o mesmo nao-terminal que esta no lado esquerdo, remova a producao
                    if (right[j] instanceof TerminalSymbol || right[j] == left) {
                        continue forExterno;
                        //remove a atual producao
                    }
                }

                //aqui a producao eh reinserida no array
                productions[next] = productions[i];
                next++;

            }
        }

        //guarda as producoes a serem analisadas junto com a posicao ate onde cada
        //producao ja foi analisada (essa analise acontece no metodo resolveDependencies)
        LRItem[] items = new LRItem[next];
        int leftIndex;

        tamanho = next;
        next = 0;

        // 1) Remove as producoes que partem de nao-terminais ja calculados (neste ponto, so estao
        //    calculados os simbolos que derivam diretamente epsilon)
        // 2) Define como nao-calculados todos os nao-terminais que aparecem nas producoes restantes
        //    2.1) Define com calculados todos os nao-terminais que nao tem producoes restantes
        for (i = 0; i < tamanho; i++) {
            leftIndex = productions[i].getLeftSide().index;

            if (!this.isNull[leftIndex]) {
                productions[next] = productions[i];
                items[next] = productions[i].items[0];
                //indica que a producao sera analisada
                //a partir do indice 0
                next++;
                this.calculados[leftIndex] = false;
                this.prodEmCalculo[leftIndex]++;
            }
        }

        // resolve as dependencias nas prodcuoes restantes
        resolveDependencies(items, next);
    }


    /**
     *  Description of the Method
     *
     *@param  items     Description of the Parameter
     *@param  numItems  Description of the Parameter
     */
    private void resolveDependencies(LRItem[] items, int numItems) {
        boolean resolvedAny;
        //indica se no ultimo laco, algum simbolo foi efetivamente calculado
        Production itemProduction;
        GrammarSymbol[] right;
        int leftIndex;
        int position;
        //, nextItem;

        do {
            resolvedAny = false;

            for (int i = 0; i < numItems; i++) {
                if (items[i] == null) {
                    continue;
                }

                position = items[i].position;
                itemProduction = items[i].production;
                leftIndex = itemProduction.getLeftSide().index;
                right = itemProduction.getRightSide();

                if (this.calculados[leftIndex]) {
                    items[i] = null;
                    this.prodEmCalculo[leftIndex]--;
                    continue;
                    //inicia uma nova iteracao do laco "for"
                }

                for (int j = position; j < right.length; j++) {
                    if (this.calculados[right[j].index] == false) {
                        break;
                    }

                    if (this.isNull[right[j].index]) {
                        position = j + 1;
                        if (position == right.length) {
                            this.calculados[leftIndex] = true;
                            this.isNull[leftIndex] = true;
                            this.prodEmCalculo[leftIndex]--;
                            items[i] = null;
                            //remove o item
                            resolvedAny = true;
                        } else {
                            items[i] = itemProduction.items[position];
                        }
                    } else {
                        items[i] = null;
                        this.prodEmCalculo[leftIndex]--;

                        if (this.prodEmCalculo[leftIndex] == 0) {
                            resolvedAny = true;
                            this.calculados[leftIndex] = true;
                            this.isNull[leftIndex] = false;
                        }
                        break;
                    }

                }
                //end for

            }
            //end for

        } while (resolvedAny);

        debug();
    }


    /**
     *  Indica se o simbolo nao-terminal pode derivar a string vazia.
     *
     *@param  symbol  Description of the Parameter
     *@return         The nullable value
     */
    public boolean isNullable(NonTerminalSymbol symbol) {
        return this.isNull[symbol.index];
    }


    /**
     *  Retorna um array onde cada indice indica se um simbolo nao-terminal
     *  especifico pode ou nao derivar a string vazia.
     *
     *@return    The nullables value
     */
    public boolean[] getNullables() {
        return this.isNull;
    }


    /**
     *  Description of the Method
     */
    private void debug() {
        NonTerminalSymbol[] simbolos = this.gramatica.getNonTerminals();
        int i;

        System.out.println("\nDEBUG:");
        System.out.print("Ja calculados:");
        for (i = 0; i < simbolos.length; i++) {
            if (this.calculados[simbolos[i].index]) {
                System.out.print(simbolos[i] + ", ");
            }
        }

        System.out.print("\nDerivam null:");
        for (i = 0; i < simbolos.length; i++) {
            if (this.isNull[simbolos[i].index]) {
                System.out.print(simbolos[i] + ", ");
            }
        }

        System.out.print("\nProducoes em calculo:");
        for (i = 0; i < simbolos.length; i++) {
            System.out.print(simbolos[i] + "(" + this.prodEmCalculo[i] + "), ");
        }
        System.out.println();
    }

}
